/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-13
 * Time: 10:04
 */
public class Test {
        public  static int mySqrt(int x) {
                if(x == 0 || x == 1){
                    return x;
                }
                int left = 0;
                int mid = (int) x/2;
                int right = x;
                int flag = 0;
                while (true){
//                    System.out.println("left ="+left+" ,mid =  "+mid+",right = "+right+",flag = "+flag);
                    if((long)mid * mid > x){
                        right = mid;
                        mid = (int) ((left + right)/2);
                    } else if ((long)mid * mid < x) {
                        left = mid;
//                        right = mid;
                        mid = (int) ((left + right)/2);
                        if(flag == mid){
                            return mid;
                        }
                        flag = mid;
                    }else {
                        return mid;
                    }
                }
        }

    public static void main(String[] args) {
        System.out.println(mySqrt(99999));
    }
}
